def max_subarray_sum(nums):
    """
    找出整数数组中子数组之和的最大值
    使用Kadane算法，时间复杂度O(n)
    """
    if not nums:
        return 0
    
    max_sum = nums[0]
    current_sum = nums[0]
    
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

def test_max_subarray_sum():
    """测试函数"""
    test_cases = [
        ([1, -2, 3, 5, -1], 8),
        ([1, -2, 3, -8, 5, 1], 6),
        ([1, -2, 3, -2, 5, 1], 7),
        ([-1, -2, -3], -1),
        ([], 0)
    ]
    
    print("最大子数组和测试：")
    for i, (nums, expected) in enumerate(test_cases):
        result = max_subarray_sum(nums)
        status = "通过" if result == expected else "失败"
        print(f"测试用例 {i+1}: {nums} => 期望:{expected}, 实际:{result} [{status}]")

if __name__ == "__main__":
    test_max_subarray_sum()